import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
         int n = scan.nextInt() ;
         int v = scan.nextInt() ;
         int[][] arr = new int[n+1][2] ; 
         for(int i=1 ; i <= n ; i ++){
            arr[i][0] = scan.nextInt();
            arr[i][1] = scan.nextInt() ;
         }
         int[][] dp = new int[n+1][v+1] ; 
         int max1 = 0 ;
         for(int i=1 ; i <= n ; i ++){
            for(int j=1 ; j<=v ; j ++){
                 dp[i][j] = dp[i-1][j] ; 
                 if(j-arr[i][0] >= 0){
                    dp[i][j] = Math.max(dp[i][j] , dp[i-1][j-arr[i][0]] + arr[i][1]) ; 
                 }
          
                 max1 = Math.max(max1 , dp[i][j]) ; 
            }
         }
          int[][] dp2 = new int[n+1][v+1] ; 
          int max2 = 0 ;
          for(int i=1 ; i<=v; i ++){
            dp2[0][i] = -1 ;
          }
            for(int i=1 ; i <= n ; i ++){
            for(int j=1 ; j<=v ; j ++){
                dp2[i][j] =  dp[i-1][j];
                if(j-arr[i][0]>=0 && dp2[i-1][j-arr[i][0]] != -1){
                    dp2[i][j] = Math.max(dp2[i][j] , arr[i][1]+dp2[i-1][j-arr[i][0]]);
                }
            }
         }
         for(int i=1 ; i <= n ; i ++){
            max2 = Math.max(max2 ,  dp2[i][v]) ;
         }
         System.out.println(max1) ; 
          System.out.println(max2) ; 



    }
}